package com.gitee.wsl.lang.bits

import com.gitee.wsl.lang.bits.api.Bits
import kotlin.math.min

/*
 * All changes to the original code are Copyright DataStax, Inc.
 *
 * Please see the included license file for details.
 */

/*
 * Original license:
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */



/**
 * BitSet of fixed length (numBits), backed by accessible ([.getBits]) long[], accessed with
 * an int index, implementing [com.gitee.wsl.lang.bits.api.Bits].
 */
class BitSet : AbstractBitSet {
    /** Expert.  */
     // Array of longs holding the bits
    val bits : LongArray

    private val numBits // The number of bits in use
            : Int
    private val numWords // The exact number of longs needed to hold numBits (<= bits.length)
            : Int

    /**
     * Creates a new LongBitSet. The internally allocated long array will be exactly the size needed
     * to accommodate the numBits specified.
     *
     * @param numBits the number of bits needed
     */
    constructor(numBits: Int = BITS_PER_WORD) {
        this.numBits = numBits
        bits = LongArray(bits2words(numBits))
        numWords = bits.size
    }

    /**
     * Creates a new LongBitSet using the provided long[] array as backing store. The storedBits array
     * must be large enough to accommodate the numBits specified, but may be larger. In that case the
     * 'extra' or 'ghost' bits must be clear (or they may provoke spurious side-effects)
     *
     * @param storedBits the array to use as backing store
     * @param numBits the number of bits actually needed
     */
    constructor(storedBits: LongArray, numBits: Int) {
        numWords = bits2words(numBits)
        require(numWords <= storedBits.size) { "The given long array is too small  to hold $numBits bits" }
        this.numBits = numBits
        bits = storedBits
        require(verifyGhostBitsClear())

    }

    override fun clear() {
        //Arrays.fill(bits, 0L)
        bits.fill(0L)
    }

    /**
     * Checks if the bits past numBits are clear. Some methods rely on this implicit assumption:
     * search for "Depends on the ghost bits being clear!"
     *
     * @return true if the bits past numBits are clear.
     */
    private fun verifyGhostBitsClear(): Boolean {
        for (i in numWords until bits.size) {
            if (bits[i] != 0L) return false
        }
        if (numBits and 0x3f == 0) return true
        val mask = -1L shl numBits
        return bits[numWords - 1] and mask == 0L
    }

    override fun length(): Int {
        return numBits
    }

    /**
     * Returns number of set bits. NOTE: this visits every long in the backing bits array, and the
     * result is not internally cached!
     */
    override fun cardinality(): Int {
        // Depends on the ghost bits being clear!
        var tot: Int = 0
        for (i in 0 until numWords) {
            tot += bits[i].countOneBits()
        }
        return tot
    }

    override fun approximateCardinality(): Int {
        // Naive sampling: compute the number of bits that are set on the first 16 longs every 1024
        // longs and scale the result by 1024/16.
        // This computes the pop count on ranges instead of single longs in order to take advantage of
        // vectorization.
        val rangeLength = 16
        val interval = 1024
        if (numWords <= interval) {
            return cardinality()
        }
        var popCount: Long = 0
        var maxWord: Int = 0
        while (maxWord + interval < numWords) {
            for (i in 0 until rangeLength) {
                popCount += bits[maxWord + i].countOneBits()
            }
            maxWord += interval
        }
        popCount *= (interval / rangeLength * numWords / maxWord).toLong()
        return popCount.toInt()
    }

    override fun get(index: Int): Boolean {
        require(index in 0..<numBits) { "index=$index, numBits=$numBits" }
        val i = index shr 6 // div 64
        // signed shift will keep a negative index and force an
        // array-index-out-of-bounds-exception, removing the need for an explicit check.
        val bitmask = 1L shl index
        return bits[i] and bitmask != 0L
    }

    override fun set(index: Int) {
        require(index in 0..<numBits) { "index=$index, numBits=$numBits" }
        val wordNum = index shr 6 // div 64
        val bitmask = 1L shl index
        bits[wordNum] = bits[wordNum] or bitmask
    }

    override fun getAndSet(index: Int): Boolean {
        require(index in 0..<numBits) { "index=$index, numBits=$numBits" }
        val wordNum = index shr 6 // div 64
        val bitmask = 1L shl index
        val `val` = bits[wordNum] and bitmask != 0L
        bits[wordNum] = bits[wordNum] or bitmask
        return `val`
    }

    override fun clear(index: Int) {
        require(index in 0..<numBits) { "index=$index, numBits=$numBits" }
        val wordNum = index shr 6
        val bitmask = 1L shl index
        bits[wordNum] = bits[wordNum] and bitmask.inv()
    }

    fun getAndClear(index: Int): Boolean {
        require(index in 0..<numBits) { "index=$index, numBits=$numBits" }
        val wordNum = index shr 6 // div 64
        val bitmask = 1L shl index
        val `val` = bits[wordNum] and bitmask != 0L
        bits[wordNum] = bits[wordNum] and bitmask.inv()
        return `val`
    }

    override fun nextSetBit(index: Int): Int {
        if (index >= numBits) {
            return NO_MORE_DOCS
        }
        require(index >= 0) { "index=$index, numBits=$numBits" }
        var i = index shr 6
        var word = bits[i] shr index // skip all the bits to the right of index
        if (word != 0L) {
            return index + word.countTrailingZeroBits()
        }
        while (++i < numWords) {
            word = bits[i]
            if (word != 0L) {
                
                return (i shl 6) + word.countTrailingZeroBits()
            }
        }
        return NO_MORE_DOCS
    }

    override fun prevSetBit(index: Int): Int {
        require(index in 0..<numBits) { "index=$index numBits=$numBits" }
        var i = index shr 6
        val subIndex = index and 0x3f // index within the word
        var word = bits[i] shl 63 - subIndex // skip all the bits to the left of index
        if (word != 0L) {
           
            return (i shl 6) + subIndex -  word.countLeadingZeroBits() // See LUCENE-3197
        }
        while (--i >= 0) {
            word = bits[i]
            if (word != 0L) {
                return (i shl 6) + 63 -  word.countLeadingZeroBits()
            }
        }
        return -1
    }

    /** this = this OR other  */
    fun or(other: BitSet) {
        or(0, other.bits, other.numWords)
    }

    private fun or(otherOffsetWords: Int, other: BitSet) {
        or(otherOffsetWords, other.bits, other.numWords)
    }

    private fun or(otherOffsetWords: Int, otherArr: LongArray, otherNumWords: Int) {
        require(otherNumWords + otherOffsetWords <= numWords) { "numWords=$numWords, otherNumWords=$otherNumWords" }
        var pos =
            min((numWords - otherOffsetWords).toDouble(), otherNumWords.toDouble()).toInt()
        val thisArr = bits
        while (--pos >= 0) {
            thisArr[pos + otherOffsetWords] = thisArr[pos + otherOffsetWords] or otherArr[pos]
        }
    }

    /** this = this XOR other  */
    fun xor(other: BitSet) {
        xor(other.bits, other.numWords)
    }

    private fun xor(otherBits: LongArray, otherNumWords: Int) {
        require(otherNumWords <= numWords) { "numWords=$numWords, other.numWords=$otherNumWords" }
        val thisBits = bits
        var pos = min(numWords.toDouble(), otherNumWords.toDouble()).toInt()
        while (--pos >= 0) {
            thisBits[pos] = thisBits[pos] xor otherBits[pos]
        }
    }

    /** returns true if the sets have any elements in common  */
    fun intersects(other: BitSet): Boolean {
        // Depends on the ghost bits being clear!
        var pos = min(numWords.toDouble(), other.numWords.toDouble()).toInt()
        while (--pos >= 0) {
            if (bits[pos] and other.bits[pos] != 0L) return true
        }
        return false
    }

    /** this = this AND other  */
    fun and(other: BitSet) {
        and(other.bits, other.numWords)
    }

    private fun and(otherArr: LongArray, otherNumWords: Int) {
        val thisArr = bits
        var pos = min(numWords.toDouble(), otherNumWords.toDouble()).toInt()
        while (--pos >= 0) {
            thisArr[pos] = thisArr[pos] and otherArr[pos]
        }
        if (numWords > otherNumWords) {
            //Arrays.fill(thisArr, otherNumWords, numWords, 0L)
            thisArr.fill(0L,otherNumWords, numWords)
        }
    }

    /** this = this AND NOT other  */
    fun andNot(other: BitSet) {
        andNot(0, other.bits, other.numWords)
    }

    private fun andNot(otherOffsetWords: Int, other: BitSet) {
        andNot(otherOffsetWords, other.bits, other.numWords)
    }

    private fun andNot(otherOffsetWords: Int, otherArr: LongArray, otherNumWords: Int) {
        var pos =
            min((numWords - otherOffsetWords).toDouble(), otherNumWords.toDouble()).toInt()
        val thisArr = bits
        while (--pos >= 0) {
            thisArr[pos + otherOffsetWords] =
                thisArr[pos + otherOffsetWords] and otherArr[pos].inv()
        }
    }

    /**
     * Scans the backing store to check if all bits are clear. The method is deliberately not called
     * "isEmpty" to emphasize it is not low cost (as isEmpty usually is).
     *
     * @return true if all bits are clear.
     */
    fun scanIsEmpty(): Boolean {
        // This 'slow' implementation is still faster than any external one could be
        // (e.g.: (bitSet.length() == 0 || bitSet.nextSetBit(0) == -1))
        // especially for small BitSets
        // Depends on the ghost bits being clear!
        val count = numWords
        for (i in 0 until count) {
            if (bits[i] != 0L) return false
        }
        return true
    }

    /**
     * Flips a range of bits
     *
     * @param startIndex lower index
     * @param endIndex one-past the last bit to flip
     */
    fun flip(startIndex: Int, endIndex: Int) {
        require(startIndex in 0..<numBits)
        require(endIndex in 0..numBits)
        if (endIndex <= startIndex) {
            return
        }
        val startWord = startIndex shr 6
        val endWord = endIndex - 1 shr 6

        /* Grrr, java shifting uses only the lower 6 bits of the count so -1L>>>64 == -1
         * for that reason, make sure not to use endmask if the bits to flip will
         * be zero in the last word (redefine endWord to be the last changed...)
         * long startmask = -1L << (startIndex & 0x3f);     // example: 11111...111000
         * long endmask = -1L >>> (64-(endIndex & 0x3f));   // example: 00111...111111
         */
        val startmask = -1L shl startIndex
        val endmask = -1L ushr -endIndex
        if (startWord == endWord) {
            bits[startWord] = bits[startWord] xor (startmask and endmask)
            return
        }
        bits[startWord] = bits[startWord] xor startmask
        for (i in startWord + 1 until endWord) {
            bits[i] = bits[i].inv()
        }
        bits[endWord] = bits[endWord] xor endmask
    }

    /** Flip the bit at the provided index.  */
    fun flip(index: Int) {
        require(index in 0..<numBits) { "index=$index numBits=$numBits" }
        val wordNum = index shr 6 // div 64
        val bitmask = 1L shl index // mod 64 is implicit
        bits[wordNum] = bits[wordNum] xor bitmask
    }

    /**
     * Sets a range of bits
     *
     * @param startIndex lower index
     * @param endIndex one-past the last bit to set
     */
     fun set(startIndex: Int, endIndex: Int) {
        require(startIndex in 0..<numBits) { "startIndex=$startIndex, numBits=$numBits" }
        require(endIndex in 0..numBits) { "endIndex=$endIndex, numBits=$numBits" }
        if (endIndex <= startIndex) {
            return
        }
        val startWord = startIndex shr 6
        val endWord = endIndex - 1 shr 6
        val startmask = -1L shl startIndex
        val endmask = -1L ushr -endIndex
        if (startWord == endWord) {
            bits[startWord] = bits[startWord] or (startmask and endmask)
            return
        }
        bits[startWord] = bits[startWord] or startmask
        //Arrays.fill(bits, startWord + 1, endWord, -1L)
        bits.fill(-1L,startWord + 1, endWord)
        bits[endWord] = bits[endWord] or endmask
    }


    override fun clear(startIndex: Int, endIndex: Int) {
        require(startIndex in 0..<numBits) { "startIndex=$startIndex, numBits=$numBits" }
        require(endIndex in 0..numBits) { "endIndex=$endIndex, numBits=$numBits" }
        if (endIndex <= startIndex) {
            return
        }
        val startWord = startIndex shr 6
        val endWord = endIndex - 1 shr 6
        var startmask = -1L shl startIndex
        var endmask = -1L ushr -endIndex

        // invert masks since we are clearing
        startmask = startmask.inv()
        endmask = endmask.inv()
        if (startWord == endWord) {
            bits[startWord] = bits[startWord] and (startmask or endmask)
            return
        }
        bits[startWord] = bits[startWord] and startmask
        //Arrays.fill(bits, startWord + 1, endWord, 0L)
        bits.fill(0L,startWord + 1, endWord)
        bits[endWord] = bits[endWord] and endmask
    }

     override fun clone(): BitSet {
        val bits = LongArray(bits.size)
        //System.arraycopy(this.bits, 0, bits, 0, numWords)
        this.bits.copyInto(bits,0,0,numWords)
        return BitSet(bits, numBits)
    }

    override fun equals(o: Any?): Boolean {
        if (this === o) {
            return true
        }
        if (o !is BitSet) {
            return false
        }
        val other = o
        return if (numBits != other.numBits) {
            false
        } else bits.contentEquals(other.bits)
        // Depends on the ghost bits being clear!
    }

    override fun hashCode(): Int {
        // Depends on the ghost bits being clear!
        var h: Long = 0
        var i = numWords
        while (--i >= 0) {
            h = h xor bits[i]
            h = h shl 1 or (h ushr 63) // rotate left
        }
        // fold leftmost bits into right and add a constant to prevent
        // empty sets from returning 0, which is too common.
        return (h shr 32 xor h).toInt() + -0x6789edcc
    }

    override fun ramBytesUsed(): Long {
        /*return BASE_RAM_BYTES_USED + RamUsageEstimator.sizeOf(bits)*/
        return 0
    }

    fun get(startIndex: Int, endIndex: Int): BitSet {
        var toIndex = endIndex

        require(startIndex in 0..<numBits) { "startIndex=$startIndex, numBits=$numBits" }
        require(endIndex in 0..numBits) { "endIndex=$endIndex, numBits=$numBits" }

        val len = length()

        // If no set bits in range return empty bitset
        if (len <= startIndex || startIndex == toIndex) return BitSet(0)

        // An optimization
        if (toIndex > len) toIndex = len

        val newLength = toIndex - startIndex

        val result = BitSet(toIndex - startIndex)

        (0..newLength).forEachIndexed { index, i ->
            if( get( startIndex + index) ) result.set(index)
        }

        return result
    }


    companion object {
        /*private val BASE_RAM_BYTES_USED: Long = RamUsageEstimator.shallowSizeOfInstance(
            FixedBitSet::class.java
        )*/

        /**
         * If the given [BitSet] is large enough to hold `numBits+1`, returns the given
         * bits, otherwise returns a new [BitSet] which can hold the requested number of bits.
         *
         *
         * **NOTE:** the returned bitset reuses the underlying `long[]` of the given `bits` if possible. Also, calling [.length] on the returned bits may return a value
         * greater than `numBits`.
         */
        fun ensureCapacity(bits: BitSet, numBits: Int): BitSet {
            return if (numBits < bits.numBits) {
                bits
            } else {
                // Depends on the ghost bits being clear!
                // (Otherwise, they may become visible in the new instance)
                val numWords = bits2words(numBits)
                var arr = bits.bits
                if (numWords >= arr.size) {
                    arr = arr.copyOf(numWords + 1)
                    //arr = ArrayUtil.grow(arr, numWords + 1)
                }
                BitSet(arr, arr.size shl 6)
            }
        }

        /** returns the number of 64 bit words it would take to hold numBits  */
        fun bits2words(numBits: Int): Int {
            // I.e.: get the word-offset of the last bit and add one (make sure to use >> so 0
            // returns 0!)
            return (numBits - 1 shr 6) + 1
        }

        /**
         * Returns the popcount or cardinality of the intersection of the two sets. Neither set is
         * modified.
         */
        fun intersectionCount(a: BitSet, b: BitSet): Long {
            // Depends on the ghost bits being clear!
            var tot: Long = 0
            val numCommonWords =
                min(a.numWords.toDouble(), b.numWords.toDouble()).toInt()
            for (i in 0 until numCommonWords) {
                //tot += java.lang.Long.bitCount(a.bits[i] and b.bits[i]).toLong()
                tot += (a.bits[i] and b.bits[i]).countOneBits()
            }
            return tot
        }

        /** Returns the popcount or cardinality of the union of the two sets. Neither set is modified.  */
        fun unionCount(a: BitSet, b: BitSet): Long {
            // Depends on the ghost bits being clear!
            var tot: Long = 0
            val numCommonWords = min(a.numWords, b.numWords)
            for (i in 0 until numCommonWords) {
                tot += (a.bits[i] or b.bits[i]).countOneBits()
            }
            for (i in numCommonWords until a.numWords) {
                tot += (a.bits[i]).countOneBits()
            }
            for (i in numCommonWords until b.numWords) {
                tot += (b.bits[i]).countOneBits()
            }
            return tot
        }

        /**
         * Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))". Neither set
         * is modified.
         */
        fun andNotCount(a: BitSet, b: BitSet): Long {
            // Depends on the ghost bits being clear!
            var tot: Long = 0
            val numCommonWords =
                min(a.numWords.toDouble(), b.numWords.toDouble()).toInt()
            for (i in 0 until numCommonWords) {
                tot += (a.bits[i] and b.bits[i].inv()).countOneBits()
            }
            for (i in numCommonWords until a.numWords) {
                tot += (a.bits[i]).countOneBits()
            }
            return tot
        }

        /** Make a copy of the given bits.  */
        fun copyOf(bits: Bits): BitSet {
            return if (bits is BitSet) {
                bits.clone()
            } else {
                val length = bits.length()
                val bitSet = BitSet(length)
                bitSet.set(0, length)
                for (i in 0 until length) {
                    if (!bits[i]) {
                        bitSet.clear(i)
                    }
                }
                bitSet
            }
        }
    }
}

